package com.dyz.leetcode._12_linkedList;

import com.dyz.leetcode.ListNode;



public class _92_reverseBetween {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        //1. 虚拟节点走left-1步，走到left节点的前一个节点
        ListNode prev = dummy;
        for(int i=0; i<left-1; i++){
            prev = prev.next;
        }

        ListNode leftNode = prev.next;
        // 2. 从 leftNode 节点开始走 right - left 步，来到 right 节点
        ListNode rightNode = leftNode;
        for(int i=0; i<right-left; i++){
            rightNode = rightNode.next;
        }

        ListNode post = rightNode.next;

        // 3. 切断得到 left 到 right 的子链表
        prev.next = null;
        rightNode.next = null;

        // 4. 反转 leftNode 到 rightNode
        reverseList(leftNode);
        // 5. 将反转后的子链表接回到原链表

        prev.next = rightNode;
        leftNode.next = post;

        return dummy.next;
    }

    // 迭代
    private void reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }

    //头插法
    public ListNode reverseBetween1(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;


        ListNode prev = dummy;
        for(int i=0; i<left-1; i++){
            prev = prev.next;
        }

        ListNode curr = prev.next;
        for(int i=0; i<right-left; i++){
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }

        return dummy.next;
    }

}
